package top.huhuiyu.ds;

/**
 * 节点版本的list简单实现
 * 
 * @author Aiden Pearce
 *
 */
public class MyList<T> {
  /**
   * 头节点
   */
  private MyNode<T> head;
  /**
   * 尾节点
   */
  private MyNode<T> tail;
  /**
   * 计数
   */
  private int count = 0;

  public boolean isEmpty() {
    return count <= 0;
  }

  public int Size() {
    return count;
  }

  public void add(T data) {
    MyNode<T> node = new MyNode<>(data);
    if (isEmpty()) {
      // 空集合添加，头尾指针都指向新进节点
      head = node;
      tail = node;
      count++;
      return;
    }
    // 接到尾节点
    tail.setNext(node);
    // 指派新节点为尾节点
    tail = node;
    count++;
  }

  public void add(int index, T data) {

    // 重载（方法名称相同，但是参数数量或者类型不同）
    if (index < 0 || index > Size()) {
      throw new RuntimeException("索引超出范围");
    }
    MyNode<T> node = new MyNode<>(data);
    // 如果是空的集合或者是添加到size()的位置，直接调用add就可以了
    if (isEmpty() || index == Size()) {
      add(data);
      return;
    }
    // 添加到0号位置的情况
    if (index == 0) {
      // 将头设置成新节点的next
      node.setNext(head);
      // 将新节点指定为新的头
      head = node;
      count++;
      return;
    }
    // 否则需要查找指定元素进行插队
    // 查找的节点默认是头
    MyNode<T> find = head;
    // 要找的是前一节点所以循环查找的次数要计数-1
    for (int i = 0; i < index - 1; i++) {
      // 向后查找
      find = find.getNext();
    }
    // 找到的是前一节点，将新节点设置为find的next,新节点next为find的next
    node.setNext(find.getNext());
    find.setNext(node);
    count++;

  }

  public T get(int index) {
    // 范围必须是0到size-1
    if (index < 0 || index >= Size()) {
      throw new RuntimeException("索引超出");
    }
    // 查找指定位置的数据，默认是0号节点（头）
    MyNode<T> find = head;
    // 查找次数就是Index的次数
    for (int i = 0; i < index; i++) {
      find = find.getNext();
    }
    return find.getData();
  }

  public T remove(int index) {
    // 范围必须是0到size-1
    if (index < 0 || index >= Size()) {
      throw new RuntimeException("索引超出");
    }
    // 移除0号（头）的情况
    if (index == 0) {
      //获取要移除的数据
      T removeData=head.getData();
      //头移动next节点
      head = head.getNext();
      count--;
      return removeData;
      
    }
    //查找移除节点的上一节点
    MyNode<T> find =head;
    for (int i = 0; i < index-1; i++) {
      find=find.getNext();
    }
    //要移除的节点
    MyNode<T> removeNode=find.getNext();
    //上一节点的next指向为移除节点的next
    find.setNext(removeNode.getNext());
    count--;
    return removeNode.getData();
  }
}
